package com.leetcode.根据数据结构分类.二叉树;

import com.leetcode.datastructure.TreeNode;

/**
 * @author: ZhouBert
 * @date: 2020/11/27
 * @description: 删除二叉搜索树中的节点
 * https://leetcode-cn.com/problems/delete-node-in-a-bst/
 */
public class B_450_删除二叉搜索树中的节点 {


	/**
	 * 不能用父节点
	 * --
	 * 这次思路有问题！
	 * 当我思路有问题的时候，应该继续确认下去，让模糊的不自信要么变得自信，要么变得直接放弃！
	 * 这样才会有新的抉择！！！
	 * --
	 * F A I L ! ! !
	 *
	 * @param root
	 * @param key
	 * @return
	 */
	public static TreeNode deleteNode(TreeNode root, int key) {
		if (root == null) {
			return null;
		}
		//指向当前节点
		TreeNode cur = root;
		//（最找删除节点）之前父节点
		TreeNode pNode = null;
		while (cur != null) {
			if (cur.val == key) {
				break;
			}
			pNode = cur;
			if (cur.val < key) {
				cur = cur.right;
			} else if (cur.val > key) {
				cur = cur.left;
			}
		}
		//此时 cur=null -> 没有找到 or cur.val=key -> 找到了
		if (cur == null) {
			return root;
		}
		//找到了并且是跟节点
		if (pNode == null) {

		}

		//对于 删除的是根节点另外考虑一下
		//进行删除
		if (cur.left == null && cur.right == null) {
			if (pNode == null) {
				return null;
			}
			//叶子节点
			if (pNode.left == cur) {
				pNode.left = null;
			} else {
				pNode.right = null;
			}
		} else if (cur.left != null && cur.right == null) {
			if (pNode == null) {
				root = cur.left;
			} else {
				if (pNode.left == cur) {
					pNode.left = cur.left;
				} else {
					pNode.right = cur.left;
				}
			}

		} else if (cur.right != null && cur.left == null) {
			if (pNode == null) {
				root = cur.right;
			} else {
				if (pNode.left == cur) {
					pNode.left = cur.right;
				} else {
					pNode.right = cur.right;
				}
			}

		} else {

			//最麻烦的是当删除节点的两个子树都存在的时候！
			//通过画图，可以发现，此时可以通过删除节点的【前驱节点】来替代删除节点的位置
			//后来才发现这里其实也是个递归！好吧并不是！
			//1.首先找到删除节点
			TreeNode parentofpre = cur;
			TreeNode predecessor = cur.left;
			TreeNode c = cur.left.right;
			while (c != null) {
				parentofpre = predecessor;
				predecessor = c;
				c = c.right;
			}

			//最方便处理的 - 将其移动到删除节点的位置
			//使用节点的位置替换实在太麻烦了！于是在老师的建议下，使用值替换！
			//TreeNode node = deleteNode(predecessor, predecessor.val);
			//进行覆盖
			cur.val = predecessor.val;

			deleteNode(cur.left, predecessor.val);
//			if (predecessor.left != null) {
//				//再次覆盖
//				predecessor.val = predecessor.left.val;
//				predecessor.left = null;
//			} else if (parentofpre.right == predecessor) {
//				parentofpre.right = null;
//			}else {
//				parentofpre.left = null;
//			}

			//此时p 就是前驱节点
//			if (predecessor.left == null) {
//				if (parentofpre != cur) {
//					parentofpre.right = null;
//				}
//
//			} else {
//				//否则，需要将 left 移动到该位置上，但是此时需要先找到前驱节点的父节点
//				TreeNode tempLeft = predecessor.left;
//				parentofpre.right = tempLeft;
//			}
//			//考虑这种情况下 删除 根节点的情况！
//			if (pNode == null) {
//				root = predecessor;
//			} else {
//				if (pNode.left == cur) {
//					pNode.left = predecessor;
//				} else {
//					pNode.right = predecessor;
//				}
//			}
//
//			if (cur.left != predecessor) {
//				predecessor.left = cur.left;
//			}
//			predecessor.right = cur.right;
//			cur.left = null;
//			cur.right = null;
		}
		return root;
	}

	/**
	 * 于是换个思路
	 * 1.首先找到 删除的节点 + 父节点
	 * 2.讨论 删除节点的情况 - 尤其需要注意左右节点都存在的情况下：有个小技巧-将前驱节点的值进行替换
	 *
	 * @param root
	 * @param key
	 * @return
	 */
	public static TreeNode deleteNodeByReplace(TreeNode root, int key) {
		TreeNode prev = null;
		TreeNode cur = root;
		while (cur != null) {
			if (cur.val == key) {
				break;
			}
			prev = cur;
			if (cur.val < key) {
				cur = cur.right;
			} else {
				cur = cur.left;
			}
		}
		if (cur == null) {
			//没有找到
			return root;
		}
		//找到了
		if (cur.left == null && cur.right == null) {
			//如果删除的是 根节点 + 此时 根节点也是叶子节点
			if (prev == null) {
				return null;
			}
			//1.叶子节点
			if (prev.left == cur) {
				prev.left = null;
			} else {
				prev.right = null;
			}
		} else if (cur.left != null && cur.right == null) {
			//如果删除的是 根节点 + 此时 根节点只有左节点
			if (prev == null) {
				root = cur.left;
				return root;
			}
			//2.只存在 左节点
			if (prev.left == cur) {
				prev.left = cur.left;
			} else {
				prev.right = cur.left;
			}
		} else if (cur.right != null && cur.left == null) {
			//如果删除的是 根节点 + 此时 根节点只有右节点
			if (prev == null) {
				root = cur.right;
				return root;
			}
			//3.只存在 右节点
			if (prev.left == cur) {
				prev.left = cur.right;
			} else {
				prev.right = cur.right;
			}
		} else {
			//4.两个节点都存在
			//找到 前驱节点 -> 用前驱节点的值覆盖 删除节点的值 ->
			TreeNode predecessor = cur.left;
			//left.right.right.right.xxx
			while (predecessor.right != null) {
				predecessor = predecessor.right;
			}
			//此时找到了前驱
			//先删除 前驱节点，再将前驱节点的值覆盖 cur
			deleteNodeByReplace(root, predecessor.val);
			cur.val = predecessor.val;
		}
		return root;
	}

	public static void main(String[] args) {
		TreeNode root = new TreeNode(5);
		root.left = new TreeNode(3);
		root.right = new TreeNode(6);
		root.left.left = new TreeNode(2);
		root.left.right = new TreeNode(4);
		root.right.right = new TreeNode(7);

//		TreeNode root = new TreeNode(4);
//		root.right = new TreeNode(7);
//		root.right.left = new TreeNode(6);
//		root.right.left.left = new TreeNode(5);
//		root.right.right = new TreeNode(8);
//		root.right.right.right = new TreeNode(9);

		//deleteNode(root, 3);


		TreeNode root2 = TreeNode.stringToTreeNode("[46,6,47,5,11,null,49,4,null,8,39,48,null,0,null,7,9,27,43,null,null,null,1,null,null,null,10,16,32,42,44,null,3,null,null,13,22,28,33,41,null,null,45,2,null,12,15,20,23,null,31,null,34,40,null,null,null,null,null,null,null,14,null,17,21,null,26,29,null,null,36,null,null,null,null,null,18,null,null,24,null,null,30,35,38,null,19,null,25,null,null,null,null,37]");
		deleteNode(root2, 43);
	}
}
